package com.chj.leetcode.tijie50to100;

import java.util.ArrayDeque;
import java.util.Deque;

public class Code84_LargestRectangleInHistogram {

	public static int maxRecSize(int[] heights) {
		if (heights == null || heights.length == 0) {
			return 0;
		}

		int maxArea = getNearLessNoRepeat(heights);
		return maxArea;
	}

	public static int getNearLessNoRepeat(int[] arr) {

		int maxArea = 0;
		int len = 0;
		Deque<Integer> stack = new ArrayDeque<>();
		for (int i = 0; i < arr.length; i++) { // i -> arr[i]
			while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
				// 当前弹出的东西 ： popIndex -> arr[popIndex]
				int popIndex = stack.pop();
				int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
//				res[popIndex][0] = leftLessIndex;
//				res[popIndex][1] = i;
				len = i - leftLessIndex + 1 - 2;
				maxArea = Math.max(len * arr[popIndex], maxArea);
			}
			stack.push(i);
		}
		while (!stack.isEmpty()) {
			int popIndex = stack.pop();
			int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
//			res[popIndex][0] = leftLessIndex;
//			res[popIndex][1] = -1;
			len = arr.length - leftLessIndex + 1 - 2;
			maxArea = Math.max(len * arr[popIndex], maxArea);
		}
		return maxArea;
	}

	public static void main(String[] args) {
		int[] arr = new int[] { 2, 1, 5, 6, 2, 3 };
		System.out.println(maxRecSize(arr));
	}
}
